<?php defined('SYSPATH') or die('No direct script access.');

/**
 * @example 三种情况
 * 节点0是虚拟节点(类似「我的电脑」)，root是指其子集（如C:盘、D:盘）
 */

class Model_Tree extends Model_Database {

	public $tablename = 'catalog';
	public $primary_key = 'cid'; //主键
	public $parent_key = 'pid'; //MySQL需加索引
	public $order_key = 'order'; //MySQL需加索引
	public $path_key = 'path'; //MySQL需加索引
	public $level_key = 'level'; //MySQL需加索引
	public $children_key = 'children';
	public $use_path = TRUE;
	public $use_order = TRUE;
	public $use_level = FALSE;


	private $index_size = 2048;//2048做一个分页

	/**
	 * 获取指定ID的Node
	 *
	 * @param  integer $cid 输入ID
	 * @return mixed      输出查询结果
	 */
	public function get_node($cid, $selector = '*')
	{
		$result = array();
		$hashkey = $cid;
		
		if (empty($cid)) //查询root属性
		{
			$result = array($this->primary_key => '0',$this->parent_key => NULL);
			$this->use_path && $result[$this->path_key] = '/0/';
			$this->use_order && $result[$this->order_key] = 0;
			$this->use_level && $result[$this->level_key] = 0;
			$result = array_keyfilter($result, $selector);
		}
		else
		{
			$selector = _array_selector_subkey($selector);
			$query = DB::select_array($selector)->from($this->tablename)->where($this->primary_key,'=',$cid);
			$result = $query->execute()->current();
		}
		if (!empty($result))
		{
			//查找子集/新order
			$query = DB::select(array(DB::expr('GROUP_CONCAT(CAST(`'.$this->primary_key.'` AS char(11)) )'),$this->children_key) )->from($this->tablename)->where($this->parent_key,'=',$cid);
			$this->use_order && $query->select(array(DB::expr('MAX(`'.$this->order_key.'`)'),$this->children_key.'_new_'.$this->order_key))->order_by($this->order_key);
			$_result = $query->execute()->current();
			$this->use_order && $result[$this->children_key.'_new_'.$this->order_key] = intval($_result[$this->children_key.'_new_'.$this->order_key]) + 1;
			$this->use_level && $result[$this->children_key.'_new_'.$this->level_key] = intval($result[$this->level_key]) + 1;
			$result[$this->children_key] = empty($_result[$this->children_key]) ? array() : explode(',', $_result[$this->children_key]);
		}

		return $result;
	}

	/**
	 * 获取所匹配的根节点Node
	 * 
	 * @param  integer $cid 需要查询的Node ID
	 * @return mixed      得到root
	 */
	public function get_root($cid, $selector = '*')
	{
		$node = $this->get_node($cid, $selector);
		if (empty($node)) return FALSE;
		if (!$this->use_path)
		{
			while(!empty($node[$this->parent_key]))
				$node = $this->get_node($node[$this->parent_key], $selector);
			return $node;
		} else {
			list(,,$rootid) = explode('/', $node[$this->path_key]); // [/0/1/2/3/] => 1
			return $this->get_node($rootid, $selector);			
		}
		return FALSE;
	}

	/**
	 * 获取父级的Node
	 * 
	 * @param  integer $cid 需要查询的Node ID
	 * @return mixed      得到父级元素
	 */
	public function get_parent($cid, $selector = '*')
	{
		$node = $this->get_node($cid, $selector);
		return empty($node) ? FALSE : $this->get_node($node[$this->parent_key], $selector);
	}

	/**
	 * 获取所匹配的祖先Nodes
	 *
	 * @param  integer $cid 需要查找的Node ID
	 * @return array     返回祖先
	 */
	public function get_parents($cid, $selector = '*')
	{
		$result = array();
		$node = $this->get_node($cid, $selector);
		while(!empty($node[$this->parent_key]))
		{
			$node = $this->get_node($node[$this->parent_key], $selector);
			$result[] = $node;
		}
		return $result;
	}

	/**
	 * 获得子集，返回一个二维数组
	 *
	 * @param integer $pid 传入父级iD
	 * @param boolean $with_id 返回的数组中是否需要以ID为key
	 * @param boolean $with_children 返回的数组中是否需要以child
	 * @return array 返回数据
	 */
	public function get_children($pid, $with_id = TRUE, $with_children = FALSE, $selector = '*')
	{

		$pid = intval($pid);$selector = _array_selector_subkey($selector);
		$query1 = DB::select(DB::expr('GROUP_CONCAT(CAST(`b`.`'.$this->primary_key.'` AS char(11)) )'))->from(array($this->tablename,'b'))->where('b.'.$this->parent_key,'=',DB::expr($this->_db->quote_column('a.'.$this->primary_key)));
		$query = DB::select_array($selector)->from(array($this->tablename,'a'))->where($this->parent_key,'=',$pid);
		if ($this->use_order)
		{
			$query1->order_by('b.'.$this->order_key);
			$query->order_by('a.'.$this->order_key);
		} 
		$with_children && $query->select(array(DB::expr('('.$query1.')'),$this->children_key));
		$result = $query->execute()->as_array($with_id ? $this->primary_key : NULL);
		if ($with_children)
			foreach ($result as &$v)
				$v[$this->children_key] = empty($v[$this->children_key]) ? array() : explode(',', $v[$this->children_key]);
			
		return $result;
	}


	/**
	 * 获得所有子(孙)集，返回一个二维数组
	 *
	 * @param integer $pid 传入父级iD
	 * @param boolean $with_id 返回的数组中是否需要以ID为key
	 * @param boolean $with_children 返回的数组中是否需要以child
	 * @return array 返回数据
	 */
	public function get_class($pid, $with_id = TRUE, $with_children = FALSE, $selector = '*')
	{

		$pid = intval($pid);
		$selector = _array_selector_subkey($selector);
		$result = array();
		if ($this->use_path)
		{
			$query1 = DB::select(DB::expr('GROUP_CONCAT(CAST(`b`.`'.$this->primary_key.'` AS char(11)) )'))->from(array($this->tablename,'b'))->where('b.'.$this->parent_key,'=',DB::expr($this->_db->quote_column('a.'.$this->primary_key)));
			$query = DB::select_array($selector)->from(array($this->tablename,'a'))->where('a.'.$this->path_key,'LIKE','%/'.$pid.'/%');
			if ($this->use_order)
			{
				$query1->order_by('b.'.$this->order_key);
				$query->order_by('a.'.$this->order_key);
			} 
			$with_children && $query->select(array(DB::expr('('.$query1.')'),$this->children_key));
			$result = $query->execute()->as_array($with_id ? $this->primary_key : NULL);
			if (empty($pid)) //如果是虚拟根节点，就添加一个
			{			
				$pointer = null;
				if ($with_id) $pointer = &$result[$pid]; else $pointer = &$result[];
				$pointer = $this->get_node($pid, $selector);
				if (!$with_children) unset($pointer[$this->children_key]); //默认有children
			}
			if ($with_children)
				foreach ($result as &$v)
					$v[$this->children_key] = empty($v[$this->children_key]) ? array() : explode(',', $v[$this->children_key]);
		}
		else
		{
			$node = $this->get_node($pid, $selector);
			$result[($node[$this->primary_key])] = $node; 
			$children = $node[$this->children_key];
			while (list(,$cid) = each($children))
			{
				$node = $this->get_node($cid, $selector);
				$result[($node[$this->primary_key])] = $node;
				foreach($node[$this->children_key] as $cid)
					$children[] = $cid;
			}
			!$with_id && $result = array_values($result);
			!$with_children && $result = array_delete_selector($result, '*/'.$this->children_key);
		}

		return $result;
	}

	public function get_class_id($pid, $with_parent = TRUE)
	{
		$pid = intval($pid);
		$result = array();
		if ($this->use_path)
		{
			$query = DB::select($this->primary_key)->from($this->tablename)->where($this->path_key,'LIKE','%/'.$pid.'/%');
			!$with_parent && $query->where($this->primary_key,'!=',$pid);
			$this->use_order && $query->order_by($this->order_key);
			$result = $query->execute()->as_array($this->primary_key);
			$result = array_values($result);
		}
		else
		{
			$with_parent && $result[] = $pid;
			$nodes = $this->get_children($pid, TRUE, FALSE, $this->primary_key);
			$children = array_keys($nodes);
			while (list(,$cid) = each($children))
			{
				$result[] = $cid;
				$nodes = $this->get_children($cid, TRUE, FALSE, $this->primary_key);
				foreach($nodes as $cid => $v)
					$children[] = $cid;
			}
		}
		return $result;
	}

	/**
	 * 获得所有子(孙)集，返回一个tree数组
	 *
	 * @param integer $pid 传入父级iD
	 * @return array 返回数据
	 */
	public function get_tree($pid, $with_parent = TRUE, $selector = '*')
	{
		$tree = $this->get_class($pid, TRUE, FALSE, $selector);
		return $this->_class_to_tree($tree, $pid, $with_parent);

	}

	/**
	 * 将上面的二维class数组生成tree，必须是设置with_id的二维数组
	 *
	 * @param mixed $items 通过_get_class获得的二维数组(with_id)
	 * @param integer $topid 提供此二维数组中的顶级节点topid
	 */
	protected function _class_to_tree($items, $topid = 0, $with_parent = TRUE)
	{
		foreach ($items as $item)
			$items[ ($item[$this->parent_key]) ][ $this->children_key ][ ($item[$this->primary_key]) ] = &$items[ ($item[$this->primary_key]) ];
		if ($with_parent)
	 		return isset($items[ $topid ]) ? $items[ $topid ] : array();
	 	else
	 		return isset($items[ $topid ][ $this->children_key ]) ? $items[ $topid ][ $this->children_key ] : array();
	}

	/**
	 * 添加一个Node,并返回其ID
	 *
	 * @param integet $pid 所属父级id
	 * @param mixed $data 数据
	 * @return integer 返回其insert id
	 */
	public function add_node($pid, $data)
	{

		$pid = intval($pid);
		$cid = 0;
		$parent = $this->get_node($pid);

		if (!empty($parent))
		{
			$data[$this->parent_key] = $pid;
			$this->use_order && $data[$this->order_key] = $parent[$this->children_key.'_new_'.$this->order_key];
			$this->use_level && $data[$this->level_key] = $parent[$this->children_key.'_new_'.$this->level_key];
			$query = DB::insert($this->tablename, array_keys($data))->values(array_values($data))->execute();
			$cid = array_shift($query);
			$this->use_path && DB::update($this->tablename)->set(array(
				$this->path_key => $parent[$this->path_key].$cid.'/',
			))->where($this->primary_key,'=',$cid)->execute();
		}

		Model_Log::log(compact('cid'));
		return $cid;
	}
	/**
	 * 删除一个node,会连带删除所有子集,并返回已被删除的ID数组,以便删除其他表的数据
	 *
	 * @param integer $cid 需要删除的Node ID
	 * @return mixed 返回此Node及其子集的id数组
	 */
	public function delete_node($cid)
	{

		$cid = intval($cid);
		$node = $this->get_node($cid);
		$cids = $this->get_class_id($cid);
		if ($this->use_path)
			DB::delete($this->tablename)->where($this->path_key,'LIKE','%/'.$cid.'/%')->execute();
		else
			DB::delete($this->tablename)->where($this->primary_key,'IN', $cids);

		Model_Log::log(compact('cids'));
		return $cids;
	}

	/**
	 * 修改一个node,无法修改pid
	 *
	 * @param integer $cid
	 * @param mixed $data 需要修改的数据
	 * @return boolean 返回操作结果
	 */
	public function update_node($cid, $data)
	{
		$cid = intval($cid);
		unset($data[$this->parent_key], $data[$this->primary_key]);
		if (empty($cid) || empty($data))
			return FALSE;
		$query = DB::update($this->tablename)->set($data)->where($this->primary_key,'=',$cid)->execute();
		Model_Log::log();
		return TRUE;
	}

	/**
	 * 更换父级
	 * @param  integer $cid
	 * @param  integet $new_pid 新父级CID
	 * @return boolean
	 */
	public function change_parent($cid, $new_pid)
	{
		$cid = intval($cid);
		if(empty($cid)) return FALSE; //报错

		$node = $this->get_node($cid);

		$new_pid = intval($new_pid);
		$new_parent = $this->get_node($new_pid);

		if (empty($new_parent) || empty($node) || $node[$this->parent_key] == $new_pid)
			return FALSE;

		if ($this->use_path)
		{
			$original_path = $node[$this->path_key];
			$new_path = $new_parent[$this->path_key] . $cid. '/';

			//将所有子集的path修改为新的
			DB::update($this->tablename)->set(array(
				$this->path_key => DB::expr('REPLACE(`'.$this->path_key.'`,\''. $original_path .'\',\'' .$new_path. '\')'),
			))->where($this->path_key,'LIKE','%/'.$cid.'/%')->execute();
		}

		if ($this->use_level)
		{
			$cids = $this->get_class_id($cid);
			//修改所有子集的level
			DB::update($this->tablename)->set(array(
				$this->level_key => DB::expr('`'.$this->level_key.'` - ('. intval($node[$this->level_key] - $new_parent[$this->children_key.'_new_'.$this->level_key]).')'),
			))->where($this->primary_key,'IN',$cids)->execute();
		}
		
		$data = array($this->parent_key => $new_pid,);
		$this->use_order && $data[$this->order_key] = $new_parent[$this->children_key.'_new_'.$this->order_key];//排列在新父级的最后
		DB::update($this->tablename)->set($data)->where($this->primary_key,'=',$cid)->execute();

		Model_Log::log();
		return TRUE;
	}

	/**
	 * 移动节点
	 * @param  integer $original_cid 原始CID
	 * @param  integer $target_cid   目标CID
	 * @param  string $move_type     [inner, prev, next]分别表示：子集、前一位、后一位
	 * @return boolean
	 */
	public function move_node($original_cid, $target_cid, $move_type = 'next') {

		$original_cid = intval($original_cid);
		$target_cid = intval($target_cid);

		if(empty($original_cid)) return FALSE; //报错

		$original_node = $this->get_node($original_cid);
		$target_node = $this->get_node($target_cid);

		if (empty($original_node) || empty($target_node))
			return FALSE;

		if ($move_type == 'inner') //成为别人子集，则直接调用,放入子集
		{
			Model_Log::log();
			return $this->change_parent($original_cid, $target_cid);
		}

		//不在同一父级,则先调到同一级,放置于节点尾巴
		if ($original_node[$this->parent_key] != $target_node[$this->parent_key])
			$this->change_parent($original_cid, $target_node[$this->parent_key]);

		if ($this->use_order)
		{
			//配置order
			$order = intval($target_node[$this->order_key]) + ($move_type == 'prev' ? 0 : 1);
			//将此Order后的子集全部加1
			DB::update($this->tablename)->set(array($this->order_key => DB::expr('`'.$this->order_key.'` + 1')))->where($this->parent_key,'=',$target_node[$this->parent_key])->and_where($this->order_key,'>=',$order)->execute();
			//修改自身的Order
			$this->update_node($original_cid,array($this->order_key => $order));
		}
		
		Model_Log::log();
		return TRUE;
	}

	public function rebuild_path($pid)
	{
		if (!$this->use_path) return FALSE;

		set_time_limit(0);
		$pid = intval($pid);

		Model_Log::$pause = TRUE;
		$node = $this->get_node($pid);
		$children = array_fill_keys($node[$this->children_key], $node[$this->path_key]);
		while(list($cid, $path) = each($children))
		{
			$this->update_node($cid, array($this->path_key => $path.$cid.'/'));
			$node = $this->get_node($cid);
			foreach($node[$this->children_key] as $cid)
				$children[$cid] = $node[$this->path_key];
			
		}
		Model_Log::$pause = FALSE;
		Model_Log::log();
		return TRUE;
	}

	public function rebuild_level($pid)
	{
		if (!$this->use_level) return FALSE;

		set_time_limit(0);
		$pid = intval($pid);

		if($this->use_path)
		{
			DB::update($this->tablename)->set(array('level' => DB::expr('LENGTH(`'.$this->path_key.'`) - LENGTH(REPLACE(`'.$this->path_key.'`,\'/\',\'\')) - 2')))->where($this->path_key,'LIKE','%/'.$pid.'/%')->execute();
		}
		else
		{
			Model_Log::$pause = TRUE;
			$node = $this->get_node($pid);
			$children = array_fill_keys($node[$this->children_key], $node[$this->children_key.'_new_'.$this->level_key]);
			while(list($cid, $level) = each($children))
			{
				$this->update_node($cid, array($this->level_key => $level));
				$node = $this->get_node($cid);
				foreach($node[$this->children_key] as $cid)
					$children[$cid] = $node[$this->children_key.'_new_'.$this->level_key];
				
			}
			Model_Log::$pause = FALSE;
		}
		Model_Log::log();
		return TRUE;
	}
	public function rebuild_order($pid, $order_by = NULL)
	{
		if (!$this->use_order) return FALSE;
		if (!is_string($order_by)) $order_by = $this->primary_key;
		
		set_time_limit(0);
		$pid = intval($pid);
		
		Model_Log::$pause = TRUE;
		$this->_db->query(Database::UPDATE, 'SELECT @t:=0');
		$children = DB::select($this->primary_key,array(DB::expr('(@t:=@t+1)'),$this->order_key))->from($this->tablename)->where($this->parent_key,'=',$pid)->order_by($order_by)->execute()->as_array($this->primary_key, $this->order_key);
		while(list($cid, $order) = each($children))
		{
			$this->update_node($cid, array($this->order_key => $order));

			$this->_db->query(Database::UPDATE, 'SELECT @t:=0');
			$nodes = DB::select($this->primary_key,array(DB::expr('(@t:=@t+1)'),$this->order_key))->from($this->tablename)->where($this->parent_key,'=',$cid)->order_by($order_by)->execute()->as_array($this->primary_key, $this->order_key);
			foreach($nodes as $cid => $order)
				$children[$cid] = $order;
		}
		Model_Log::$pause = FALSE;

		Model_Log::log();
		return TRUE;
	}

	public function build_index()
	{
		$data = $this->get_tree(0, TRUE, array($this->primary_key, $this->parent_key)); //只要主键、父键
		$list = $this->_rev_build_index($data);
		unset($data);

		$_keys = array_keys($list);
		$_data = array_chunk($list, $this->index_size);
		unset($list);
		
		$page_count = count($_data);
		$this->set_cache('tree-index-count', $page_count);
		for ($i = 0; $i < $page_count; $i++)
			$this->set_cache('tree-index-page-'.$i, implode('', $_data[$i]));
		unset($_data);

		array_unshift( $_keys, 'N'.count($_keys) );
		$str = call_user_func_array('pack', $_keys);
		$this->set_cache('tree-index', $str);

		return $str;
	}

	private function _rev_build_index(&$node)
	{
		$result = array();
		$result[ ($node[$this->primary_key]) ] = pack('N3', $node[$this->primary_key], $node[$this->parent_key], count($node[$this->children_key]));

		foreach ($node[$this->children_key] as &$value)
		{
			$_node = $value;
			$result[ ($_node[$this->primary_key]) ] = pack('N3', $_node[$this->primary_key], $_node[$this->parent_key], count($_node[$this->children_key]));
			if (!empty($_node[$this->children_key]))
				$result = array_merge($result, $this->_rev_build_index($value));
		}

		return $result;
	}

}
